package 剑指offer;

import java.util.Scanner;

/** 

* @author ：soulstones
* @version ：2019年9月30日 下午9:51:52 
* @Description：
* 
求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
*/
public class A31整数中1出现的次数 {
	  public static int NumberOf1Between1AndN_Solution(int n) {

	//采用数学归纳总结规律。可以将n这个数划分为个位，十位，百位，千位等等。
		  ///个位：  在个位数上，1会每隔10出现一次，如1，11，21。在以10为一个阶段时，每个完整的阶段里面都会有一个1.
		              //例如22，可以分为3个阶段，0-9，10-19，20-22（不完整的阶段）。可以知道，在不完整的阶段中，如果它的最后一个个位数小于1，就不可能出现1了（这个归纳同样适用于其他的数字）
		              // 个位上的1:   n/10*1+（n%10!=0? 1:0）  即每个能被10整除的部分每隔10就会出现一个1，在余数中（结果必然是0-9中的一个），如果不为0，那肯定是在（1-9）中，1必然出现一次。
		  
		  //十位：十位数上出现1的情况是10-19，它们会每个100出现一次，这次以100为阶段。
		  			//	例如317，同样的0-99，100-199，200-299，300-317（不完整）。在完整阶段中都会出现10次1，分析不完整阶段，如果露出来的数大于19，直接就是10个1了，因为10-19肯定会出现。如果小于10，就不会出现十位上的1了
		  			    //设置 k为不完整阶段上的数字   k=n%100
		  				// (n/100)*10+if(k>=19) 10 else if(k<10) 0 else if(10<=k<19)  k-10+1   (11中出现两次1 )
		  //百位：100-199都会出现百位1，一共出现100次，阶梯间隔为1000
		  			//假设2139，0-999，1000-1999，2000-2139  （不完整）
		  			//k=n%1000
		    		//  (n/1000)*100+ if(k>199) 100 else if(k<100) 0  else if(100<=k<199)  k-100+1
		        //千百万位依次类推
		  
		  
		  //个位数上1的个数为：n / 10 * 1 + (if(k > 1) 1 else if(k < 1) 0 else k - 1 + 1)
		  //十位上的：count(i) = (n / (i * 10)) * i + (if(k > i * 2 - 1) i else if(k < i) 0 else k - i + 1)
		  //百千位：sum1 = sum(count(i))，i = Math.pow(10, j), 0<=j<=log10(n)
		  //归纳：    …………                                     min(max(n  mod (i*10)-i+1,0),i)
		  
		if (n <= 0)
			return 0;
		int count = 0;
		for (long i = 1; i <= n; i *= 10) {                  //依次是个位，十位，百位，千位
			long diviver = i * 10;
			count += (n / diviver) * i + Math.min(Math.max(n % diviver - i + 1, 0), i);
		}
		return count;
	}
   
	  public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int res = NumberOf1Between1AndN_Solution(n);
		System.out.println(res);
	}
}
